struct Solution {}

fn main() {}

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        let mut dp: Vec<i32> = vec![];
        dp.push(0);
        dp.push(1);
        dp.push(2);
        if n < 3 {
            return dp[n as usize];
        }
        for i in 3..=n {
            dp.push(dp[(i - 2) as usize] + dp[(i - 1) as usize])
        }
        dp[n as usize]
    }
}